package com.jiang.专题.动态规划.Q673;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/29 20:51
 */
class Solution {
    public int findNumberOfLIS(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len][2]; // dp[i][0] 表示递增序列的长度，dp[i][1] 表示递增序列的个数

        int maxLen = 0;
        for (int i = 0; i < len; i++) {
            dp[i][0] = 1;
            dp[i][1] = 1;
            int j = i - 1;
            while (j >= 0) {
                if (nums[i] > nums[j]) { // 后面的数大于前面的数
                    if (dp[i][0] == dp[j][0] + 1) { // 如果加了nums[j]后递增序列长度一样，则个数加dp[j][1]
                        dp[i][1] += dp[j][1];
                    } else if (dp[i][0] < dp[j][0] + 1){// 如果加了nums[j]后递增序列变长，则个数为dp[j][1]
                        dp[i][0] = dp[j][0] + 1;
                        dp[i][1] = dp[j][1];
                    }
                }
                j--;
            }
            maxLen = Math.max(dp[i][0], maxLen);
        }

        int res = 0;
        for (int i = 0; i < len; i++) {
            if (dp[i][0] == maxLen) res += dp[i][1];
        }
        return res;
    }
}
